Consensus Prerequisites and Two Generals' Problem

This chapter lays the foundation of the consensus problem in distributed systems. By consensus, we mean that a set of processes start a protocol where each of them has a choice of possible decisions, and all of them reach a common decision by exchanging network messages. Achieving consensus is easy if there are no failures (network or node failures). However, achieving consensus under different kinds of failures becomes challenging (or even impossible). While extensive research has been done to solve the consensus problem, we have picked three celebrated results for discussion in this chapter. These results are as follows:

• The Two Generals’ Problem

• The FLP impossibility

• The Byzantine Generals Problem

We believe the above results give us ample background for the rest of the chapters in this course.

In this lesson, we will define the consensus problem more formally and review two important system models (synchronous and asynchronous) and different kinds of faults (crash-stop and Byzantine faults). After that, we’ll discuss the Two Generals’ Problem.

Consensus #

We need consensus for many computational tasks. Let's take the examples of distributed databases and data replication.

The use of databases is commonplace, and many rely on the abstraction of transactions to work correctly. A database transaction is involved when we purchase goods or services from any online store or conduct a bank withdrawal or deposit. Transactions are impossible without a consensus where, for example, money is deducted from one account and deposited into another as one logical unit. The consensus here involves either all parties moving ahead with the transaction and committing it, or none of the parties moving ahead and aborting the translation.

The second example is data replication to increase durability under data losses or corruption threats. Each copy of data must remain consistent at all places, even when we allow data mutations. Doing so is only possible when all replicas have a consensus on specific values.

Formally, the consensus among $n$ processes that can choose a value from a permissible set of values is to satisfy the following three conditions:

1. Validity: If every nonfaulty process starts with an initial value $v$, their final decision must be $v$. This condition helps us exclude trivial solutions to a consensus where, for example, no matter what, every process chooses a fixed value.

2. Termination: Every participating non-faulty process must make a decision eventually. Upon termination of a consensus protocol, we are sure we have reached a final stable state.

3. Agreement: The final decision of every process must be the same, hence the consensus.

To formally study the consensus problem, we need to make assumptions about the execution environment of the processes.

Computational models#

We are primarily concerned with two major components in a distributed system—the nodes and the network. They can exhibit different characteristics and provide different guarantees to their users. Researchers have broadly grouped them into two classes of synchronous and asynchronous models.

In the synchronous model, we assume the following:

1. Processes either work in lockstep or have a maximum fixed bound of how far ahead or behind one process can be from the other. This implies that a process takes bounded time to complete its steps. A process might fail but does not further participate in the algorithm once it has failed.

2. The clocks on the processes are perfectly synchronized or have fixed known bounds on the skew.

3. The network delivers the message in a known upper-bound time.

Multi-core systems that share the same system clock and the cores of a GPU working in lock-step exhibit the properties of the synchronous model (albeit arguably, such systems might not be considered a distributed system).

In an asynchronous model, we assume the following:

1. Processes are concurrently working at varying, relative speeds from each other. A process might pause for an unspecified amount of time before responding again to other processes.

2. Processes neither have synchronized clocks nor have the drift on the clocks fixed.

3. There is no upper bound in terms of time on the arrival of the messages. A message might be delayed arbitrarily. The absence of a message from a process cannot be taken as a sure sign of the termination of a process.

Many large-scale systems connected via the global internet might exhibit one or more properties of the asynchronous model.

Faults#

Failures are a norm for large-scale systems—something is always broken. To manage these failures, fault tolerance is a primary tenet of modern system design. For example, to guard against data corruption and loss, we often replicate data at multiple places such that failures are not correlated. The consensus among replicas is necessary to achieve consistent replication.

For the formal study of failures, researchers have developed many fault models. In a distributed system, failures can occur at the nodes or the network connecting them. For node failures, one end of the failure spectrum is stopping failures—where when a node fails, it stops working and does not produce any erroneous results. The other end of the failure spectrum can be modeled as Byzantine faults, which means that nodes can exhibit arbitrary behavior. We can consider that dealing with faults becomes challenging as we move from stopping failures to Byzantine kinds of failures. (Many other faults models exist between these two ends of the failure spectrum. Though for our purposes, knowing about stopping failures and Byzantine failures is sufficient.)

Crash faults#

In a crash failure, a node can suddenly stop working without giving any early warning of impending failure. Such a node will not receive or respond to any network messages from any entity. That implies that such nodes cannot produce any erroneous values once failed.

Note: In distributed systems literature, there are some faults called fail-stop failures. A node in a fail-stop fault does not actively participate in any computation, though it might receive network messages and might reply to them. Such a system helps other entities to easily detect that a specific node has failed. Though in our discussion, we’ll consider crash failures because they are a better representation of real-world scenarios. For more details, see the spectrum of failure models here.

Byzantine faults#

In a Byzantine fault, nodes can exhibit arbitrary behavior and output erroneous or malicious outputs. Such nodes might act as non-faulty nodes if they sense something detecting them. Isolating such nodes in a large system can be challenging or impossible. Certain kinds of software bugs and hardware failures can make a node fall into the Byzantine faults category. Still, at other times, a node might be acting as a Byzantine node under the control of a malicious entity.

Network faults#

A network like the internet can have many issues, such as:

• Corrupting network packets

• Losing network packets

• Reordering a stream of packets from sender to receiver

• Delaying a network packet for delivery

• Network link failures and router failures cause network partitions

In a synchronous setting, packet delivery is assumed to have a maximum upper bound time. In an asynchronous setting, it is assumed that packets can be delayed arbitrarily long.

The Two Generals’ Problem#

We now have sufficient background to discuss our first problem—the Two Generals' Problem. This problem assumes a synchronous computational model, where the nodes have no faults, but the network connecting them can lose messages. This problem shows that consensus is impossible to achieve between just two parties under such a model. It is a strong result saying that even under the nice settings of a synchronous model, achieving consensus can be impossible under network failures. Let's discuss this problem in detail.

The Two Generals' Problem assumes that the fault model is non-Byzantine, which means that the nodes are assumed to be either correct or crash-stop. However, the messages may be intercepted, and there is a possibility that a message may not reach the intended recipient. The problem arises when one General needs to decide whether to attack or retreat but cannot be sure that the other General has received the message. If they both attack, the fort will be conquered, but if they both retreat, nothing will happen. However, the attack will fail if one attacks while the other retreats.

This problem illustrates the challenge of achieving consensus in a distributed system where messages may be lost. The Generals cannot be completely sure that they have achieved consensus. This is a fundamental limitation of consensus algorithms in distributed systems, which designers must consider when developing such systems. Achieving consensus is crucial to ensure a robust and resilient distributed system.

The fundamental difficulty here is that a General cannot distinguish between the following two scenarios. If we try to devise an algorithm for a consensus of decision from General 1's perspective, there are two choices for general 1.

• General 1 always attacks after sending the attack message: If General 2 receives the message and both attack, we have a consensus. Though if the original message is lost (scenario 2 above), General 1 would be alone in the battle. General 1 might increase the probability of a message getting through by sending a lot of messengers. However, there is no guarantee of consensus because all of the messages might get lost.

• General 1 only attacks if it receives an acknowledgment from General 2: In scenario 1 above, for such an algorithm, General 2 will find itself alone in the battle, or if General 2 also waits for the acknowledgment of the acknowledgment, both of them might never attack because they will be in an infinite chain of sending an acknowledgment of the acknowledgment.

So we see there is no way to guarantee consensus here.

Two Generals' Problem applied in real life#

Let's take an example of an online store, where customers buy goods, pay via their credit cards, and goods are dispatched. This setting resembles the Two Generals’ Problem. The network can lose messages. The following picture shows four possible scenarios, but only one is correct (card charged and goods dispatched) that needs consensus between the two parties. Now in real life, if we are in a bad scenario, we use outside guards. For example, if a card is charged, but the goods are not delivered due to some issue, we reverse the charge and send the customer an apology email with possibly a coupon to avert the customer's anger. If the card was not charged, the charge could be retried later, or the matter can be arbitrated by the payment system. This example shows us how to approach impossibility results for real applications.

Note: Fischer and Lynch showed that consensus is possible in $f+1$ rounds if there can be $f$ crash-stop kind of node failures in a synchronous model. The simple idea is that each node can broadcast its decision and all the decisions it has received so far to all other nodes. Eventually, all non-faulty nodes converge on a single decision. Note that we are assuming that the network is non-faulty. In the literature, this result is often known as FL82.

In summary, we now know that consensus is impossible when nodes are non-faulty, but the network can lose the messages (Two Generals' Problem). Consensus is possible if the network is non-faulty, but nodes can exhibit crash failures (FL82). In the next lesson, we turn to the asynchronous model and show that even a single crash-stop failure can stop the rest of the nodes from reaching a consensus—yet another impossibility result, commonly known as FLP.